package com.github.why168;


public class LinkList {
    public static void main(String[] args) {
        java.util.LinkedList<Integer> jdkLinkList = new java.util.LinkedList<Integer>();
        jdkLinkList.add(0, 1);
        jdkLinkList.add(2);
        jdkLinkList.add(3);
        jdkLinkList.add(4);
        jdkLinkList.add(5);
        jdkLinkList.add(6);
        jdkLinkList.add(7);
        jdkLinkList.add(8);
        jdkLinkList.add(9);
        jdkLinkList.add(10);
        jdkLinkList.add(11);
//        jdkLinkList.get(0);
//        jdkLinkList.remove()
//        jdkLinkList.remove("11");
//        jdkLinkList.removeFirst();
//        jdkLinkList.removeLast();
//        jdkLinkList.element();
//        jdkLinkList.peek();
//        jdkLinkList.poll();
//        jdkLinkList.offer(1);
        for (int i = 0; i < jdkLinkList.size(); i++) {
            Integer integer = jdkLinkList.get(i);
            System.out.println(integer);
        }
//        ListIterator<Integer> integerListIterator = jdkLinkList.listIterator();
//        while (integerListIterator.hasNext()) {
//            System.out.println(integerListIterator.next());
//        }

//
//        Map<Object, Object> hashMap = Collections.synchronizedMap(new HashMap<Object, Object>());
//        hashMap.put(null, "null");
//        hashMap.put("null", null);
//        System.out.println(hashMap.get(null));
//        System.out.println(hashMap.get("null"));
//
//        HashSet hashSet = new HashSet();
//        hashSet.add(1);
//
//        Hashtable hashtable = new Hashtable(); // k\v不能为null
//        hashtable.put(null, null);
//
//        LinkedHashMap linkedHashMap;

        LinkList linkList = new LinkList();
        linkList.add("element00");
        linkList.add("element01");
        linkList.add("element02");
        linkList.add("element03");
        linkList.add("element04");
        linkList.add("element05");
        linkList.add("element06");

        for (int i = 0; i < linkList.size; i++) {
            System.out.println(linkList.get(i));
        }
        linkList.remove(1);
        linkList.remove(linkList.size - 1);
        System.out.println("---");
        for (int i = 0; i < linkList.size; i++) {
            System.out.println(linkList.get(i));
        }

    }

    transient int size = 0;
    transient Node first;
    transient Node last;

    public static class Node {
        public Node prev; // 上一个节点
        public String element;
        public Node next; // 下一个节点

        public Node(Node prev, String element, Node next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
    }

    private String remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    private String get(int index) {
        checkElementIndex(index);
        return node(index).element;
    }

    private Node node(int index) {
        // 二分查查找法
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    private void checkElementIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    private void add(int index, String element) {
        checkElementIndex(index);

        if (size == index) {
            linkLast(element);
        } else {
            linkBefore(element, node(index));
        }
    }

    private boolean add(String element) {
        linkLast(element);
        return true;
    }

    private void linkBefore(String element, Node node) {
        Node prev = node.prev;
        Node newNode = new Node(prev, element, node);
        node.prev = newNode;
        if (prev == null) {
            first = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
    }

    private String unlink(Node node) {
        String element = node.element;
        Node next = node.next;
        Node prev = node.prev;

        // 前节点
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null;
        }

        // 后节点
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

        node.element = null;
        size--;
        return element;
    }

    private String unlinkLast(Node node) {
        String element = node.element;
        Node prev = node.prev;
        node.element = null;
        node.prev = null;

        last = prev;
        if (prev == null) {
            first = null;
        } else {
            prev.next = null;
        }
        size--;
        return element;
    }

    private String unlinkFirst(Node node) {
        String element = node.element;
        Node next = node.next;
        node.element = null;
        node.next = null;

        first = next;
        if (next == null) {
            last = null;
        } else {
            next.prev = null;
        }
        size--;
        return element;
    }

    private void link(Node node) {

    }

    private void linkLast(String e) {
        Node l = last;
        Node newNode = new Node(l, e, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    private void linkFirst(Node node) {

    }

}
